package offer;

import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * @Author Elephas
 * @Date 2022/1/29
 **/
@FunctionalInterface
public interface HighestPeak {
    int[][] highestPeak(int[][] isWater);
}

class HighestPeakImpl1 implements HighestPeak{
    final static int[][] TEST_01 = new int[][]{{0,0,1},{1,0,0},{0,0,0}};
    public static void main(String[] args) {
        new HighestPeakImpl1().highestPeak(TEST_01);
    }

    /**
     * 考虑分水岭算法，第一次扫描找到所有的水域，由这些水域出发进行广度优先搜索，多余每个点至多遍历两次，矩阵为 m x n 维，时间复杂度 o(mn),
     * @param isWater
     * @return
     */
    @Override
    public int[][] highestPeak(int[][] isWater) {
        M = isWater.length;
        N = isWater[0].length;
        int[][] ans = new int[M][N];
        Queue<Point> pointQueue = new LinkedList<>();

        // 初始化返回矩阵，ans[i][j] >= 0 时表示高度， ans[i][j] = -1 时表示未访问
        initQueue(pointQueue,isWater,ans);
        while(!pointQueue.isEmpty()){
            int currentSize = pointQueue.size();
            for (int i = 0; i < currentSize; i++) {
                Point temp = pointQueue.poll();
                if(isValidPoint(new Point(temp.x - 1,temp.y))){
                    if(ans[temp.x - 1][temp.y] == NOT_VISITED) {
                        ans[temp.x - 1][temp.y] = ans[temp.x][temp.y] + 1;
                        pointQueue.add(new Point(temp.x-1,temp.y));
                    }
                }
                if(isValidPoint(new Point(temp.x + 1,temp.y))){
                    if(ans[temp.x + 1][temp.y] == NOT_VISITED) {
                        ans[temp.x + 1][temp.y] = ans[temp.x][temp.y] + 1;
                        pointQueue.add(new Point(temp.x + 1,temp.y));
                    }
                }
                if(isValidPoint(new Point(temp.x ,temp.y - 1))){
                    if(ans[temp.x][temp.y - 1] == NOT_VISITED) {
                        ans[temp.x][temp.y - 1] = ans[temp.x][temp.y ] + 1;
                        pointQueue.add(new Point(temp.x,temp.y - 1));
                    }
                }
                if(isValidPoint(new Point(temp.x ,temp.y + 1))){
                    if(ans[temp.x][temp.y + 1] == NOT_VISITED) {
                        ans[temp.x][temp.y + 1] = ans[temp.x][temp.y] + 1;
                        pointQueue.add(new Point(temp.x,temp.y + 1));
                    }
                }
            }
        }
        return ans;
    }
    static int M;
    static int N;
    static final int NOT_VISITED = -1;
    private boolean isValidPoint(Point p){
        if((p.x >= 0 && p.x < M) && (p.y >=0 && p.y <N)){
            return true;
        }else{
            return false;
        }
    }
    private void initQueue(Queue<Point> pointQueue,int[][] isWater,int[][] ans){
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if(isWater[i][j] == 1){
                    pointQueue.add(new Point(i,j));
                    ans[i][j] = 0;
                }else{
                    ans[i][j] = NOT_VISITED;
                }
            }
        }
    }
    class Point{
        int x;
        int y;
        public Point(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
}
